// 二分搜索(英语：binary search), 也叫折半搜索(英语：half-interval search), 是一种在有序数组中查找特定元素的搜索算法.

package main

func binarySearch(array []int, target int, lowIndex int, highIndex int) int {
    if highIndex < lowIndex {
        return -1
    }
    mid := int(lowIndex + (highIndex-lowIndex)/2)
    if array[mid] > target {
        return binarySearch(array, target, lowIndex, mid)
    } else if array[mid] < target {
        return binarySearch(array, target, mid+1, highIndex)
    } else {
        return mid
    }
}

func iterBinarySearch(array []int, target int, lowIndex int, highIndex int) int {
    startIndex := lowIndex
    endIndex := highIndex
    var mid int
    for startIndex < endIndex {
        mid = int(startIndex + (endIndex - startIndex))
        if array[mid] > target {
            endIndex = mid
        } else if array[mid] < target {
            startIndex = mid
        } else {
            return mid
        }
    }
    return -1
}


